// 313.超级丑数
package Leetcode_Second_Brush;

public class Solution313 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // 1. dp[i] 表示第 i 个丑数
        int[] dp = new int[n];

        // 2. 初始化，第一个丑数为 1
        dp[0] = 1;

        // 3. 当前各个因子指针
        int[] pointer = new int[primes.length];

        // 4. 状态转移
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                // 防止溢出
                if (dp[pointer[j]] <= Integer.MAX_VALUE / primes[j])
                    min = Math.min(min, dp[pointer[j]] * primes[j]);
            }
            dp[i] = min; // 赋值
            // 指针后移
            for (int j = 0; j < primes.length; j++) {
                // 防止溢出
                if (dp[pointer[j]] <= Integer.MAX_VALUE / primes[j] && dp[pointer[j]] * primes[j] == dp[i])
                    pointer[j]++;
            }
        }

        return dp[n - 1];
    }
}
